Leetcode 767. 重构字符串 C++

#Leetcode 767. 重构字符串 C++| 来源: 网络整理| 查看: 265

题目描述

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = “aab” 输出: “aba” 示例 2:

输入: S = “aaab” 输出: “” 注意:

S 只包含小写字母并且长度在[1, 500]区间内。

解答

贪心算法，只需要不停的取出现次数最多的元素和出现次数第二多的元素，不断将其加入string中就可以。 priority_queue自动排序。这里定义一个pair，会自动按照pair的第一维 int 按照从大到小排序。参考：https://blog.csdn.net/sinat_15723179/article/details/80896214

class Solution { public: string reorganizeString(string S) { string res; map m; for(char c : S) m[c]++; priority_queue pq; for(auto mem : m) { if(mem.second-1 > S.size()-mem.second) return ""; else { pq.push({mem.second, mem.first}); } } pair p1; pair p2; while(pq.size()>1) { p1=pq.top(); pq.pop(); p2=pq.top(); pq.pop(); res+=p1.second; res+=p2.second; if(--p1.first>0) pq.push({p1.first,p1.second}); if(--p2.first>0) pq.push({p2.first,p2.second}); } if(pq.size()==1) { pair p1=pq.top(); if(p1.first>1) return ""; else res+=p1.second; } return res; } };

【本文地址】

公司简介

联系我们